package sword_offer;

import common.Node;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName _35copyRandomList
 * @Description: 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 示例 2：
 *
 *
 *
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 * 示例 3：
 *
 *
 *
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 * 示例 4：
 *
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 *  
 *
 * 提示：
 *
 * -10000 <= Node.val <= 10000
 * Node.random 为空（null）或指向链表中的节点。
 * 节点数目不超过 1000 。
 *  
 *
 * 注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/13 10:19
 */
public class _35copyRandomList {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.next = node2;
        node2.next = node3;

        node2.random = node1;
        Node node = new _35copyRandomList().copyRandomListSplit(node1);
        System.out.println(node);
    }

    // 开辟一个额外空间存储旧节点和新节点的绑定关系，时间复杂度和空间复杂度都是O(n)
    public Node copyRandomListMap(Node head) {
        if (head == null)
            return null;
        Node sourceCursor = head;
        Node targetHead = new Node(0);
        Node targetCursor = targetHead;// 构建头节点，然后创建头节点游标 逐步向后移动;
        Map<Node, Node> map = new HashMap<>();

        // 遍历head，然后创建新的head，并存储到二者对应关系到Map中
        while (sourceCursor != null){
            // 创建节点并维护新节点之间的关系
            Node newNode = new Node(sourceCursor.val);
            targetCursor.next = newNode;
            targetCursor = targetCursor.next;

            // 维护Map
            map.put(sourceCursor, newNode);

            sourceCursor = sourceCursor.next;
        }

        // 处理random指向关系
        sourceCursor = head;
        targetCursor = targetHead.next;
        while (sourceCursor != null){
            if (sourceCursor.random == null){
                // 如果不需要维护random关系，直接移动两个链表的指针
                sourceCursor = sourceCursor.next;
                targetCursor = targetCursor.next;
                continue;
            }

            Node randomNode = sourceCursor.random;
            targetCursor.random = map.get(randomNode);

            sourceCursor = sourceCursor.next;
            targetCursor = targetCursor.next;
        }

        return targetHead.next;
    }


    // 拼接 + 处理 + 裁剪， 时间复杂度是O(n)，空间复杂度是O(1)，必须分在三个步骤中去做，第二步和第三部不可以混在一起，否则裁剪时候会引起链表指向关系混乱
    public Node copyRandomListSplit(Node head) {
        if (head == null)
            return null;

        // 遍历head 并将新构建的节点储存进去
        Node sourceCursor = head;
        while (sourceCursor != null){
            Node nextNode = sourceCursor.next;

            Node newNode = new Node(sourceCursor.val);
            sourceCursor.next = newNode;
            newNode.next = nextNode;

            sourceCursor = nextNode;
        }

        // 处理random指向关系
        sourceCursor = head;

        while (sourceCursor != null){
            if (sourceCursor.random != null){
                sourceCursor.next.random = sourceCursor.random.next;
            }
            sourceCursor = sourceCursor.next.next;
        }

        // 拆分链表
        sourceCursor = head;
        Node targetHead = new Node(1);
        Node targetCursor = targetHead;
        while (sourceCursor != null){
            targetCursor.next = sourceCursor.next;
            targetCursor = targetCursor.next;

            // 这里只是移动了游标位置，并没有改变原始的head节点之间的指向关系
            sourceCursor.next = sourceCursor.next.next;

            sourceCursor = sourceCursor.next;
        }


        return targetHead.next;
    }
}
